// 给定一个数组nums，元素值只有0,1,2，分别代表红色，白色，蓝色，将数组排序，使得红色在前，白色在中间，蓝色在最后

// 思路：双指针，left和right，left左边都是0， right右边都是2
// 时间复杂度：O(n)
// 空间复杂度：O(1)

function sortColors(arr) {
    let left = 0
    let right = arr.length - 1
    let index = 0
    while (index <= right) {
        if (arr[index] === 0) {
            [arr[left], arr[index]] = [arr[index], arr[left]];
            left++
            index++
        } else if (arr[index] === 2) {
            [arr[right], arr[index]] = [arr[index], arr[right]];
            right--
        } else {
            index++
        }
    }
    return arr
}

let arr = [2, 0, 2, 1, 1, 0]
sortColors(arr)
console.log(arr)